#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
string s;
int st[100];
int k, n;
int main()
{
	int t;
	cin >> t;
	while (t--) {
		cin >> n >> k;
		cin >> s;
		memset(st, 0, sizeof(st));
		for (int i = 0; i < s.size(); i++) {
			if (s[i] >= 'a' && s[i] <= 'z') {
				int v = s[i] - 'a';
				st[v]++;
			}
			else {
				int v = s[i] - 'A';
				st[v + 32]++;
			}
		}
		int ans1 = 0;
		int ans2 = 0;
		for (int i = 0; i < 32; i++) {
			ans1 += min(st[i], st[i + 32]);
			ans2 += abs(st[i] - st[i + 32]) / 2;
		}
		cout << ans1 + min(ans2, k) << endl;
	}
	return 0;
}